package com.future.light.hello.dt.chap03.sequencelist;

/**
 * 链表节点Node
 * @author zhushijie
 *
 * @param <T>
 */
class Node<T> {
	private Node<T> next = null;
	private T data;
	
	public Node (T data){
		this.data = data;
	}
	
	public Node<T> getNext() {
		return next;
	}
	public void setNext(Node<T> next) {
		this.next = next;
	}
	public T getData() {
		return data;
	}
	public void setData(T data) {
		this.data = data;
	}
}

/**
 * 单向链表
 * @author zhushijie
 *
 * @param <T>
 */
public class LinkList<T> {
	private Node<T> header = new Node<T>(null);
	
	/**
	 * 获得指定位置的节点值（假设指定位置比链表长度小）
	 * @param index
	 * @return
	 */
	public T getElem(int index){
		Node<T> temp = null;
		if(header.getNext() != null){
			temp = header.getNext();
			for(int i = 0; i < index; i++){
				if(temp.getNext() != null)
					temp = temp.getNext();
			}
		}
		return temp.getData();
	}
	
	public String toString(){
		String str = "";
		if(header.getNext() != null){
			Node<T> temp = header.getNext();
			while(temp != null){
				str = str + temp.getData() + " ";
				temp = temp.getNext();
			}
		}
		return str;
	}
	
	/**
	 * 在指定位置插入节点
	 * @param index 从0开始
	 * @param o 节点对象
	 */
	public void insertElem(int index, Node<T> o){
		Node<T> temp = null;
		if(header.getNext() == null){
			header.setNext(o);
		}else{
			if(index == 0){
				o.setNext(header.getNext());
				header.setNext(o);
			}else{
				temp = header.getNext();
				for(int i = 0; i < index-1; i++){
					temp = temp.getNext();
				}
				if(temp.getNext() == null){
					temp.setNext(o);
				}else{
					o.setNext(temp.getNext());
					temp.setNext(o);
				}
			}
		}
	}
	
	/**
	 * 删除一个指定位置的节点
	 * @param index
	 * @return
	 */
	public T delElem(int index){
		Node<T> temp = null;
		Node<T> delNode = null;
		if(header.getNext() != null){
			if(index == 0){
				delNode = header.getNext();
				header.setNext(delNode.getNext());
				return delNode.getData();
			}else{
				temp = header.getNext();
				for(int i = 0; i < index - 1; i++){
					temp = temp.getNext();
				}
				delNode = temp.getNext();
				temp.setNext(temp.getNext().getNext());
			}
		}
		return delNode.getData();
	}

	public static void main(String[] args) {
		LinkList<Integer> t = new LinkList<Integer>();
		Node<Integer> n0 = new Node<Integer>(0);
		Node<Integer> n1 = new Node<Integer>(1);
		Node<Integer> n2 = new Node<Integer>(2);
		Node<Integer> n3 = new Node<Integer>(3);
		Node<Integer> n4 = new Node<Integer>(4);
		Node<Integer> n5 = new Node<Integer>(5);
		t.insertElem(0, n0);
		t.insertElem(1, n1);
		t.insertElem(2, n2);
		t.insertElem(3, n3);
		t.insertElem(4, n4);
		t.insertElem(5, n5);
		System.out.println(t.toString());
//		System.out.println(t.getElem(3));
		System.out.println(t.delElem(5));
		System.out.println(t.toString());
	}

}
